//leetcode


//https://leetcode.cn/problems/largest-1-bordered-square/


//前缀和


class Solution {
public:
    vector<vector<int>> s;

    int get(int x1, int y1, int x2, int y2) 
    {
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];//算出子矩阵的大小
    }

    int largest1BorderedSquare(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        s = vector<vector<int>>(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + g[i - 1][j - 1];

        for (int len = min(n, m); len > 1; len -- )//枚举大矩阵长度,先不判断变长为1的矩阵
        {
            for (int i = 1; i + len - 1 <= n; i ++ ) //枚举x
            {
                for (int j = 1; j + len - 1 <= m; j ++ ) //枚举y
                {
                    int a = i, b = j, c = i + len - 1, d = j + len - 1;//(a,b)是左上角,(c,d)是右下角
                    if (get(a, b, c, d) - get(a + 1, b + 1, c - 1, d - 1) == 4 * (len - 1)) //画图,这个4*(len-1)很有用
                    {
                        return len * len;
                    }
                }
            }
        }

        if (s[n][m] > 0) return 1;//如果二维前缀和大于0那么此时的最大矩阵情况就是1

        return 0;
    }
};
